This paper considers the problem of matrix completion when some number of thecolumns are completely and arbitrarily corrupted, potentially by a maliciousadversary. It is well-known that standard algorithms for matrix completion canreturn arbitrarily poor results, if even a single column is corrupted. Onedirect application comes from robust collaborative filtering. Here, some numberof users are so-called manipulators who try to skew the predictions of thealgorithm by calibrating their inputs to the system. In this paper, we developan efficient algorithm for this problem based on a combination of a trimmingprocedure and a convex program that minimizes the nuclear norm and the$\ell_{1,2}$ norm. Our theoretical results show that given a vanishing fractionof observed entries, it is nevertheless possible to complete the underlyingmatrix even when the number of corrupted columns grows. Significantly, ourresults hold without any assumptions on the locations or values of the observedentries of the manipulated columns. Moreover, we show by aninformation-theoretic argument that our guarantees are nearly optimal in termsof the fraction of sampled entries on the authentic columns, the fraction ofcorrupted columns, and the rank of the underlying matrix. Our results thereforesharply characterize the tradeoffs between sample, robustness and rank inmatrix completion.
展开▼
